import typing


# 题目：给一根长度为n的绳子，把绳子渐成m段，每段绳子的长度记为k[0], k[1], k[2],....k[m] 请问k[0], k[1], k[2],....k[m]的可能的最大乘积是多少？

# 首先是动态规划算法，可以定义f(n)为长度为n的绳子的切段以后各段乘积的最大值,在剪第一刀的时候，有n-1种选择（n个点中间的空格)
# 所以有f(n) = max(f(i) *f(n-i)) 0<i<n

def max_product(length):
    if length<2:
        return 0
    elif length == 2:
        return 1
    elif length == 3:
        return 2
    else:
        product = [0 for i in range(length+1)]
        product[0], product[1], product[2], product[3] = 0, 1, 2, 3
        res = 0
        for i in range(4, length+1):
            res = 0
            for j in range(i//2 +1):
                tmp = product[j] * product[i-j]
                if tmp > res:
                    res = tmp
            product[i] = res
        res = product[length]
        return res


if __name__ == '__main__':
    print(max_product(8))